package problems.daily;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 792. 匹配子序列的单词数
 * <p>https://leetcode.cn/problems/number-of-matching-subsequences/</p>
 *
 * @author habitplus
 * @since 13:54, 2022/11/17
 */
public class DT792 {

    public int numMatchingSubseq(String s, String[] words) {
        if (s == null || s.length() < 1 || words == null || words.length < 1) return 0;

        int ret = 0;
        ArrayList<Integer>[] list = new ArrayList[26];

        int j;
        for (int i = 0; i < s.length(); ++i) {
            j = s.charAt(i) - 'a';
            if (list[j] == null) {
                list[j] = new ArrayList<Integer>();
            }
            list[j].add(i);
        }


        for (String w : words) {
            if (handle(list, w)) {
                ++ret;
            }
        }

        return ret;

    }

    private boolean handle(ArrayList<Integer>[] pos, String s) {
        if (s == null || s.length() < 1) return false;

        // 记录 每个小写字母上一次出现的位置
        int[] pre = new int[26];

        Arrays.fill(pre, -1);

        int k = -1;
        int j, sz;

        for (char c : s.toCharArray()) {
            j = c - 'a';
            // 没有当前字符
            if (pos[j] == null || pos[j].size() < 1) {
                return false;
            }

            ++pre[j];
            sz = pos[j].size();
            while (pre[j] < sz && pos[j].get(pre[j]) <= k)
                ++pre[j];

            // 未找到合适的位置
            if (pre[j] >= pos[j].size()) return false;

            k = pos[j].get(pre[j]);

        }

        return true;
    }
}
